package Arrays;

/**
 * 作者:hfj
 * 功能:70.爬楼梯
 * 日期: 2025/10/22 8:52
 */
public class ClimbStairs {
    public static void main(String[] args) {
        System.out.println(climbStairs1(45));
    }

    //递归方法会超时异常
    public static int climbStairs(int n) {
        if (n == 1){
            return 1;
        }else if (n == 2){
            return 2;
        }else {
            return climbStairs(n-1) + climbStairs(n-2);
        }
    }

    //使用斐波那契数
    public static int climbStairs1(int n) {
        if (n == 1){
            return 1;
        }
        if (n == 2){
            return 2;
        }
        int a = 1,b = 2,sum = 0;
        for (int i = 3; i <= n; i++) {
            sum = a+b;
            a = b;
            b = sum;
        }
        return sum;
    }
}
